本章介绍 KNN（k-最近邻）和决策树的原理、关键参数以及优缺点，重点展示相关的数学公式，以便深入理解其工作机制。

---

1. KNN (k-Nearest Neighbors)

1.1 原理

KNN 是一种基于实例的懒惰学习算法，其核心思想是通过计算测试样本与训练样本之间的距离，找到最近的 k 个样本，进行分类或回归：

• 分类：最近 k 个样本中多数类别决定测试样本的类别。
• 回归：通过最近 k 个样本的平均值或加权平均值预测测试样本的值。

距离度量

常见的距离度量方法：

• 欧几里得距离：适用于数值型数据。
• 曼哈顿距离：适用于数值型数据。
• 汉明距离：适用于分类变量。

公式

关键参数

• k 值：控制最近邻样本的数量。
  • k 值过小：对噪声敏感，可能过拟合。
  • k 值过大：可能引入过多无关样本，导致欠拟合。
• 加权 KNN：给距离较近的样本赋予更高权重。

加权公式

在加权 KNN 中，距离较近的样本具有更高的权重：
wi = 1/d(x_m,x_i)^2
其中 d(x_m,x_i)为测试点 x_m与训练样本 x_i 的距离。

k 值的选择

可以按照part_1最后介绍的几种方法进行选择，如：通过网格搜索找到指定指标最优时的k值

1.2 优缺点

优点：

• 简单易实现。
• 适合处理非线性问题。
• 对异常值鲁棒（当 k 值足够大时）。

缺点：

• 计算成本高，尤其是大数据集。
• 不适用于高维数据（维度灾难）。

---

2. 决策树 (Decision Tree)

2.1 原理

决策树是一种基于树结构的模型，通过递归划分数据集来构建分类或回归模型：

• 内部节点：测试某个属性。
• 分支：属性的可能值。
• 叶节点：类别或预测值。

划分标准

• 信息增益：通过熵的减少量衡量属性的重要性。
• 增益率：信息增益的归一化形式，避免偏向多值属性。
• 基尼指数：衡量数据集的纯度，越小越好。

2.2 优缺点

优点：

• 模型直观易解释。
• 适合处理连续和离散数据。
• 对缺失值和噪声具有一定鲁棒性。

缺点：

• 容易过拟合，生成复杂的树。
• 对数据分布变化敏感。

2.3 停止条件

决策树的构建通常在以下条件下停止：

• 节点中的样本全属于同一类别。
• 没有更多的属性可供划分。
• 树的深度达到预设限制。

---

3. 示例分析

KNN 例题 1

题目：已知如下数据集，k=3，预测点为 (2, 2)：

样本点	坐标 (x, y)	类别
A	(1, 1)	+
B	(2, 1)	-
C	(4, 3)	+
D	(3, 3)	-

解答步骤：

---

KNN 例题 2

题目：假设数据为分类变量，使用汉明距离计算最近邻。

样本点	属性 1	属性 2	类别
A	高	男	+
B	中	女	-
C	高	女	+

测试点：(高, 女)。

解答步骤：

---

决策树例题 1

题目：使用信息增益选择划分属性。

天气	温度	玩游戏
晴	热	是
晴	热	否
阴	适中	是
雨	凉爽	否

解答步骤：略（就是我懒了，自己算一下吧）

答案：选择“天气”作为划分属性。

---

决策树例题 2

题目：使用基尼指数选择划分属性。

属性 A	属性 B	类别
高	是	+
低	否	-
中	是	+

解答步骤：略（就是我懒了，自己算一下吧）

答案：选择“属性 A”作为划分属性。